'''
https://leetcode.cn/problems/house-robber/
'''
from functools import cache
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def f(i):
            if i >= n:
                return 0
            return max(nums[i] + f(i+2), f(i+1))
        return f(0)

    # DP 打表
    def rob2(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 2)
        for i in range(n-1, -1, -1):
            dp[i] = max(nums[i] + dp[i+2], dp[i+1])
        return dp[0]

    # 状态压缩
    def rob3(self, nums: List[int]) -> int:
        n = len(nums)
        a = b = 0
        for i in range(n-1, -1, -1):
            c = max(nums[i] + b, a)
            b = a
            a = c
        return a
